The invention relates generally to the fields of computers, hardware architecture, and software.
Software bugs and viruses are a major impediment to the operation of computers. Workflow problems are caused. Data is lost. Expenditures are made to address computer failures. These problems lead to significant expenses. The expenses incurred for software debugging with the widespread use of computers are a billion dollar economic problem, with businesses, schools, and government carrying a large load of the economic expenditures related to software debugging and computer operation.
Recent impressive improvements in computer architecture have not led to significant gains in ease of debugging and security. Software debugging and attack detection often rely on inserting run-time software checks. However, program execution typically slows down significantly, often by 10-100 times.
Despite costly efforts to improve software-development methodologies, software bugs in deployed codes continue to thrive, often accounting for as much as 40% of computer system failures, and 50-70% of security vulnerabilities. Software bugs can crash systems, making services unavailable or, in the form of “silent” bugs, corrupt information or generate wrong outputs. This lapse represents a major shortcoming in state-of-the-art microprocessors. Software bugs, especially memory-related bugs, are often exploited by malicious users to launch security attacks.
There are several approaches to debug codes to improve software robustness and security. One approach is to perform checks statically. Examples of this approach include explicit model checking and program analysis. Most static tools require significant involvement of the programmer to write specifications or annotate programs. In addition, most static tools are limited by aliasing problems and other compile-time limitations. This is especially the case for programs written in unsafe languages such as C or C++, the predominant programming languages in the art. As a result, many bugs often remain in programs even after aggressive static checking and are exploited for security attacks.
Another approach is to monitor execution dynamically. Many methods have been proposed for dynamic code monitoring. Dynamic monitoring can be generally classified into two categories: code-controlled monitoring (CCM) and location-controlled monitoring (LCM).
With CCM, monitoring is performed only at special points in the program. Two types of CCM are assertions and (most) dynamic checkers. Assertions are inserted by programmers to perform sanity checks at certain places. If the condition specified in an assertion is false, the program aborts. Assertions are one of the most commonly used methods for debugging. However, they can add significant overhead to program execution. Moreover, it is often hard to identify all the places where assertions should be placed.
Dynamic checkers are automated tools that detect common bugs at run time, with instrumentation inserted in the code that monitors invariants and reports violations as errors or alerts for attacks. The strength of this approach is that the analysis is based on actual execution paths and accurate values of variables and aliasing information.
For example, DIDUCE automatically infers likely program invariants, and uses them to detect program bugs. Others, such as Purify and Valgrind, monitor memory accesses to detect memory leaks and some simple instances of memory corruption, such as freeing a buffer twice or reading an uninitialized memory location. StackGuard can detect some buffer overflow bugs, which have been a major cause of security attacks. Another dynamic checker, Eraser, can detect data races by dynamically tracking the set of locks held during program execution. Such dynamic checker tools usually use compilers or code-rewriting tools such as ATOM, EEL, and Dyninst to instrument programs with checks.
Unfortunately, most dynamic checkers suffer from two general limitations. First, they are often computationally expensive. One major reason is their large instrumentation cost. Another reason is that dynamic checkers may instrument more places than necessary due to lack of accurate information at instrumentation time. As a result, some dynamic checkers slow down a program, e.g., by 6-30 times, which makes such tools undesirable for production runs. Moreover, some timing-sensitive bugs may never occur with these slowdowns. Additionally, such high overhead is not practical to use during production runs to detect security attacks.
Second, most dynamic checkers rely on compilers or pre-processing tools to insert instrumentation and, therefore, are limited by imperfect variable disambiguation. Consequently, particular accesses to a monitored location may be missed by these tools. Because of this, some bugs are caught much later than when they actually occur, which makes it hard to find the root cause of the bug. The following C code gives a simple example.
int x, *p;/* assume invariant : x = 1 */. . .p = foo( );/* a bug: p points to x incorrectly */*p = 5;/* line A: corruption of x */. . .InvariantCheck (x == 1);  /* line B */z = Array(x);. . .
While x is corrupted at line A, the bug is not detected until the invariant check at line B. This is because it may be hard for a dynamic checker to know that it needs to insert an invariant check after line A, due to the difficulty of performing perfect pointer disambiguation. Generally, dynamic checkers often suffer from hard-coded bug detection functionality, language specificity, and difficulty to work with low-level code.
With LCM, on the other hand, monitoring is associated directly with memory locations, and therefore all accesses to such memory locations are monitored. LCM has two advantages over CCM. First, LCM monitors all accesses to a watched memory location using all possible variable names or pointers, whereas CCM may miss some accesses because of pointer aliasing. Second, LCM monitors only those memory locations that truly access a watched memory location, while CCM may need to instrument at many unnecessary points due to the lack of accurate information at instrumentation time. Therefore, LCM can be used to detect both invariant violations and illegal accesses to a memory location, whereas it may be difficult and too expensive for CCM to check for illegal accesses.
Hardware-assisted watchpoints fall into the LCM category. For example, to assist software debugging, several state-of-the-art processor architectures such as Intel and Sun SPARC provide hardware support for watchpoints to monitor several programmer-specified memory locations. The hardware support is provided through a few special debug registers. When a watched memory location is accessed, the hardware triggers an exception that is handled by the debugger (such as gdb). It is then up to the programmer to manually check the program state using the debugger.